LeetCode 654、最大二叉树

一、题目描述

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

• 二叉树的根是数组 nums 中的最大元素。
• 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
• 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树 。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 通过递归的操作可以构建出最大二叉树
        return traversal( nums , 0 , nums.length - 1 );
    }

    private TreeNode traversal( int[] nums, int left, int right ){

        // 递归终止条件
        // 当前区间没有元素
        if (left > right) return null;

        // 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
        if ( left == right ) return new TreeNode(nums[left]);

        // 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
        int maxValueIndex = left;

        // 遍历 [ left + 1 , right ] 这个区间，找出  [ left , right ] 这个区间的最大值
        for ( int i = left + 1 ; i <= right ; i++){
            
            // 更新 maxValueIndex
            if(nums[i] > nums[maxValueIndex]){
                maxValueIndex = i;
            }
        }

        // root 是数组 nums 在  [ left , right ] 这个区间中的最大元素
        TreeNode root = new TreeNode(nums[maxValueIndex]);

        // 根据 maxValueIndex，划分为  [ left , maxValueIndex - 1 ] 
        // 递归的构建这个区间的二叉树
        TreeNode leftNode = traversal(nums,left,maxValueIndex - 1);
        
        // 根据 maxValueIndex，划分为  [ maxValueIndex - 1 , right] 
        // 递归的构建这个区间的二叉树
        TreeNode rightNode = traversal(nums,maxValueIndex + 1,right);

        // leftNode 为 root 的左子树
        root.left = leftNode;

        // rightNode 为 root 的右子树
        root.right = rightNode;

        // 返回结果
        return root;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution
{
public:
    TreeNode *constructMaximumBinaryTree(vector<int> nums)
    {
        // 通过递归的操作可以构建出最大二叉树
        return traversal(nums, 0, nums.size() - 1);
    }

    TreeNode *traversal(vector<int>& nums, int left, int right)
    {

        // 递归终止条件
        // 当前区间没有元素
        if (left > right)
            return NULL;

        // 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
        if (left == right)
            return new TreeNode(nums[left]);

        // 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
        int maxValueIndex = left;

        // 遍历 [ left + 1 , right ] 这个区间，找出  [ left , right ] 这个区间的最大值
        for (int i = left + 1; i <= right; i++)
        {

            // 更新 maxValueIndex
            if (nums[i] > nums[maxValueIndex])
            {
                maxValueIndex = i;
            }
        }

        // root 是数组 nums 在  [ left , right ] 这个区间中的最大元素
        TreeNode *root = new TreeNode(nums[maxValueIndex]);

        // 根据 maxValueIndex，划分为  [ left , maxValueIndex - 1 ]
        // 递归的构建这个区间的二叉树
        TreeNode *leftNode = traversal(nums, left, maxValueIndex - 1);

        // 根据 maxValueIndex，划分为  [ maxValueIndex - 1 , right]
        // 递归的构建这个区间的二叉树
        TreeNode *rightNode = traversal(nums, maxValueIndex + 1, right);

        // leftNode 为 root 的左子树
        root->left = leftNode;

        // rightNode 为 root 的右子树
        root->right = rightNode;

        // 返回结果
        return root;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # 通过递归的操作可以构建出最大二叉树
        return self.traversal( nums , 0 , len(nums) - 1 ) 
    
    def traversal(self, nums: List[int] , left : int ,right : int) -> TreeNode:

        # 递归终止条件
        # 当前区间没有元素
        if  left > right : 
            return None 

        # 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
        if left == right :
            return  TreeNode(nums[left]) 

        # 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
        maxValueIndex = left 

        # 遍历 [ left + 1 , right ] 这个区间，找出  [ left , right ] 这个区间的最大值
        for i in range(left + 1 , right + 1) : 
            # 更新 maxValueIndex
            if nums[i] > nums[maxValueIndex] :
                maxValueIndex = i 
            
        

        # root 是数组 nums 在  [ left , right ] 这个区间中的最大元素
        root = TreeNode(nums[maxValueIndex]) 

        # 根据 maxValueIndex，划分为  [ left , maxValueIndex - 1 ] 
        # 递归的构建这个区间的二叉树
        leftNode = self.traversal(nums,left,maxValueIndex - 1) 
        
        # 根据 maxValueIndex，划分为  [ maxValueIndex - 1 , right] 
        # 递归的构建这个区间的二叉树
        rightNode = self.traversal(nums,maxValueIndex + 1,right) 

        # leftNode 为 root 的左子树
        root.left = leftNode 

        # rightNode 为 root 的右子树
        root.right = rightNode 

        # 返回结果
        return root